package wtx.geeks;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;
/**
 * https://www.spoj.com/problems/COINS/
 */
public final class BytelandianGoldCoins {
  // 尽管coin最大是10亿，但是返回值可能远远超过10亿！
  private static Map<Integer, Long> maxChangeMap = new HashMap<>();
  public static long maxChange(int coin) {
    if (coin <= 1) {
      return coin;
    }
    if (maxChangeMap.containsKey(coin)) {
      return maxChangeMap.get(coin);
    }
    long maxChange = coin;
    long change1 = maxChange(coin/2) + maxChange(coin/3) + maxChange(coin/4);
    if (maxChange < change1) {
      maxChange = change1;
    }
    maxChangeMap.put(coin, maxChange);
    return maxChange;
  }
   
    /**
     * Says hello to the world.
     * @param args The arguments of the program.
     */
  public static void main(String[] args) {
    Random rnd = new Random(3263);

    for (int n = 0; n < 10; ++n) {
      int c = rnd.nextInt(100);
      System.out.println(String.format("coin: %d, max profit = %d", c, maxChange(c)));
    }
  }
}
